package com.hx.app.leetcode.com.hx.longestsubstringwithoutrepeatingcharacters;

/**
 * @author hx 2022/7/4 14:31
 */
public class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new Solution();
        // String s = "abcabcbb";
        // String s = "bbbbb";
        // String s = "pwwkew";
        // String s = "dvdf";
        // String s = "tmmzuxt";
        String s = "zwnigfunjwz";
        int num = solution.lengthOfLongestSubstring(s);
        System.out.println(num);
    }
}

class Solution {

    /*public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>(16);
        int max = 0;
        int num = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, i);
                max = Math.max(++num, max);
            } else {
                i = map.get(c);
                map.clear();
                num = 0;
            }
        }
        return max;
    }*/

    /*public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>(16);
        int max = 0;
        int num = 0;

        int lastSameLocation = -1;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                max = Math.max(++num, max);
            } else {
                if (map.get(c) < lastSameLocation) {
                    max = Math.max(++num, max);
                } else {
                    num = i - (lastSameLocation = map.get(c));
                }
            }
            map.put(c, i);
        }
        return max;
    }*/

    public int lengthOfLongestSubstring(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for (int i = 0; i < 128; i++) {
            last[i] = -1;
        }

        int max = 0;
        int window = 0;
        //tmmzuxt
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i);
            // if (last[c] != -1) {
            //     window = Math.max(last[c] + 1, window);
            // }
            window = Math.max(last[c] + 1, window);
            max = Math.max(i - window + 1, max);
            last[c] = i;
        }
        return max;
    }
}